﻿#pragma once
#include "Index.h"

class MinimumWindowSubstring
{
public:
    /**
     * 最小覆盖子串.
     * https://leetcode.cn/problems/minimum-window-substring/ 
     * 哈希 字符串 滑动窗口
     *
     * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
	 * 注意：
     * 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
	 * 如果 s 中存在这样的子串，我们保证它是唯一的答案。
     */
	std::string minWindow(std::string s, std::string t)
	{
		if (s.empty() || t.empty() || s.size() < t.size())
			return "";
		const int sSize = s.size();
		const int tSize = t.size();

		//在t中出现的不同字符
		std::unordered_set<char> uniqueChars;
		//前26个字符'A'~'Z' 后26个字符'a'~'z'
		std::vector<int> differ(52, 0);
		for (int i = 0; i < tSize; ++i)
		{
			differ[charToIndex(t[i])]--;
			uniqueChars.insert(t[i]);
		}

		//未满足条件的字符数
		int failedChars = uniqueChars.size();
		//满足结果的最小覆盖子串
		int ansLeft = -1, ansSize = INT_MAX;

		int left = 0;
		for (int right = 0; right < sSize; ++right)
		{
			if (uniqueChars.count(s[right]) == 0)
				continue;

			//拓展右边界
			int& differOfRight = differ[charToIndex(s[right])];
			if (differOfRight == -1)
				failedChars--;
			differOfRight++;

			//收缩左边界
			bool shrinkLeft;
			do
			{
				shrinkLeft = false;
				if (uniqueChars.count(s[left]) == 0)
				{
					left++;
					shrinkLeft = true;
				}
				else
				{
					int& differOfLeft = differ[charToIndex(s[left])];
					if (differOfLeft > 0)
					{
						differOfLeft--;
						left++;
						shrinkLeft = true;
					}
				}
			} while (shrinkLeft);

			//找到结果
			if (failedChars == 0 && (right - left + 1) < ansSize)
			{
				ansLeft = left;
				ansSize = right - left + 1;
			}
		}

		if (ansLeft >= 0)
			return s.substr(ansLeft, ansSize);
		else
			return "";
	}
private:
    inline int charToIndex(const char& ch)
    {
		if (ch < 'a')
			return ch - 'A';
		else
			return ch - 'a' + 26;
    }
};


#ifdef DEV_TEST
#include <gtest/gtest.h>
TEST(MinimumWindowSubstringTest, minWindow)
{
    MinimumWindowSubstring solution;
    std::string s = "ADOBECODEBANC", t = "ABC";
    auto result = solution.minWindow(s, t);
    EXPECT_EQ(result, "BANC");
}
#endif